package Solutions;


import java.util.*;

/**
 * 在给定的数组中找出他的一个最长子数组，要求该数组相邻的两个数 a ,b 满足：
 * condition：a % b == 0 || b % a == 0
 */

public class IntelligentWarehouse {

    public List<Integer> intelligentWarehouse(int[] nums) {
        // 当数组的长度为1 的时候，直接返回即可，其本身一定是自己的倍数
        if (nums.length == 1) return Collections.singletonList(nums[0]);
        Map<Integer, List<Integer>> map = new HashMap<>();// 用于储存所有满足条件的子数组
        int res;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums.length - i <= result) {
                // 如果开始指针后面的元素个数比当前得到的结果还小，则表明后续不会产生比当前结果更大的子数组
                return map.get(result);
            }
            res = 1;
            List<Integer> tmp = new ArrayList<>();// 用于记录每次遍历得到的子数组
            tmp.add(nums[i]);
            for (int before = i, later = before + 1; before < nums.length - 1 && later < nums.length; ) {
                if (nums[later] * 1.0 % nums[before] == 0 || nums[before] * 1.0 % nums[later] == 0) {
                    // 如果满足条件，则把新的元素添加到tmp中，前指针移动到后指针处，后指针后移一位
                    res++;
                    tmp.add(nums[later]);
                    before = later;
                    later = before + 1;
                } else {
                    // 如果不满足，则后指针往后移动一位
                    later++;
                }
            }
            map.put(res, tmp);
            result = Math.max(res, result);
        }
        return map.get(result);
    }

    public static void main(String[] args) {
        System.out.println(new IntelligentWarehouse().intelligentWarehouse(new int[]{4, 4, 2, 8, 5, 800, 4, 1, 2}));
    }
}
